package Test.offer;


/**
 * @ClassName P54
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/2 11:26
 * @Version 1.0
 */
public class P54 {
    int index = 0;

    public Node KthNode(Node root, int k) {
      if (root == null || k < 0) {
          return null;
      }
      Node node = getKthNode(root, k);
      return node;
    }

    private Node getKthNode(Node root, int k) {
        if (root == null || k < 0) {
            return null;
        }
        Node node = getKthNode(root.left, k);
        if (node != null) return node;

        index++;
        if (index == k) return root;

        node = getKthNode(root.right, k);
        if (node != null) return node;

        return null;
    }

    class Node {
        Node left;
        Node right;
        int val;

        Node(int val) {
            this.val = val;
        }
    }
}
